package 笔试;

import java.util.ArrayList;

public class 岛屿数量和距离 {
    static int max = Integer.MIN_VALUE;
    public int[][] nextP= {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public int numIslands(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        boolean[][] flag = new boolean[grid.length][grid[0].length];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1) {
                    count++;
                    dfs(grid, i, j, new ArrayList<>());
                }
            }
        }
        return count;
    }

    public void dfs(int[][] grid, int i, int j, ArrayList<int[]> list) {
        grid[i][j] = 2;
        for(int[] pre : list) {
            int tmpX = Math.abs(pre[0]-i);
            int tmpY = Math.abs(pre[1]-j);
            int tmp = (int)Math.sqrt(tmpX*tmpX + tmpY*tmpY);
            max = Math.max(tmp, max);
        }
        list.add(new int[]{i, j});
        for(int z = 0; z < 4; z++) {
            int nI = i + nextP[z][0];
            int nJ = j + nextP[z][1];
            if(nI < 0 || nI >= grid.length || nJ < 0 || nJ >= grid[0].length) {
                continue;
            }
            if(grid[nI][nJ] == 1) {
                dfs(grid, nI, nJ, list);
            }

        }
    }
}
